googologywikiaorg-20200223-history
User blog:Koteitan/Categorizing of the rule sets for all sub versions of bashicu matrix
This is the table of the rule sets of (almost) all sub versions of Bashicu Matrix invented in 2015-2018. The aim of this entry is the comparison of the rule sets of them. The all sub versions can be categorized according to the difference of the three micro rules; Bad root searching rules, Bad part ascending rules and Ascension modification rules. In this article, the all sub versions are re-written in the mathematical definition with the same format. So that the comparison become easier. Please use this for your proof of the termination or analysis. Rule set Rule sets Authors Dates Definitions Bad root searching Bad part ascending Ascension modification discussions BM1 Bashicu 21,August'15 *BASIC code Left method All branches enabled No modify *explanation with equations *non-terminated example(hyp/^,cos) *non-terminated example(Bubby3) *countermeasure(bashicu) *It is said that (0,0)(1,1)(2,1)(3,1)(2,0)(1,1)(2,1)(3,1) is the smallest non-terminated matrix. rTSS rpakr 25.March'18 *definition Left method All branches enabled No modify same as trio sequence of BM1 BM1.1The rule doesn't have the formal name so that I named it as BM1.1 in this article. Bashicu 18,March'16 *BASIC code Upper-branch-ignoring-model All branches enabled No modify *Non-terminated example(hyp/^,cos) *Countermeasure(bashicu) BM2.1 koteitan 4.March'18 *C code Upper-branch-ignoring-model All branches enabled No modify *same as BM1.1 *non-terminated example(KurohaKafka) 12 Bubby3's fix Bubby3 25,March'18 *Definition Upper-branch-ignoring-model All branches enabled No modify same as BM1.1 BM2 Bashicu 25,June'16 *BASIC code Upper-branch-ignoring-model BM2 based no modify *explain in SlideShare (in Japanese) *explain by rpakr(in Japanese) *discussion for proof by KurohaKafka(Japanese) *discussion for proof by fish(Japanese) analysing link(Bashicu, Deedlit11, 84.229.92.191, 77.127.67.249, KurohaKafka, Alemagno12, Googleaarex, Bubby3, rpakr) BM2.3 koteitan Nish Ecl1psed 18,Jun'18 *C code *First explanation(in Japanese) Upper-branch-ignoring-model Upper-branch-ignoring-model no modify *example of which the expansion is different from BM2 *I made it to be more logical because I feel the bad part ascending rule of BM2 is complicating. *I heard Nish and Ecl1psed made same algorithm independently. BM3.1 Nish 18,July'18 *conversation on Discord *introduction Upper-branch-ignoring-model BM2-based all 1 or (1,0,…,0) *Though its ascending rule is weaker than BM2, It is believed that it catch up BM2 and it is easy to analyze. BM3.2 Nish 23,July'18 *Conversation on Discord *introduction Upper-branch-ignoring-model Upper-branch-ignoring-model all 1 or (1,0,…,0) *Though its ascending rule is weaker than BM2.3, It is believed that it catch up BM2.3 and it is easy to analyze. BM3.1.1 Ecl1psed 20,July'18 *Conversation on Discord *introduction Upper-branch-ignoring-model BM2-based all 1 or all 0 *It can causes dangerous sequence as (2,0)(4,0) so that it is believed to be non-terminated. BM2.2 koteitan 8,March'18 *Definition *C code Concestor method All branches enabled No modify *Analysis by Bubby3 *Nish said \((0,0,0)(1,1,1)\) is weaker than \(\zeta_0\). *I made it by the changing bad root searching rule because I feel BM2's rule is complicating I should change the bad part ascending rule. Settings *Bashicu matrix consist a matrix whose element is the natural number and a natural number named bracket. *The matrix \(\begin{pmatrix}c_{11}&c_{12}\\c_{21}&c_{22}\end{pmatrix}\) in the Bashicu matrix is often described as \((c_{11},c_{21})(c_{12},c_{22})\). In this page it is describe so. *\(f(n)\) is the function from a natural number into a natural number. in BM1, rTSS, BM1.1, Bubby3's fix, BM2, \(f(n)=n^2\)and in BM2.1, BM2.2, BM2.3 \(f(n)=n+1\). Common rules A expansion procedure of a Bashicu matrix in a step is shown as below: #Let the rightmost column be \(C=(c_1, c_2, \cdots c_N)\). #If the all elements of \(C\) is \(0\), The bad root is not found and the Jump to 6. #Let the index of the lowermost non-zero element of the \(C\) be \(t\). (\(c_t\gt 0\land \forall k(k\gt t\rightarrow c_k=0)\)) #Decide the bad root \(R=(r_1, r_2, \cdots, r_N)\) with the bad root searching rule of the rule set. #remove the rightmost column \(C\). #If the bat root is not found, replace \(n\) into \(f(n)\) and end the expansion procedure. #let the bad root \(R\) and the partial matrix in the right side of it be the bad part \(B=(b_{11},b_{21},\cdots,b_{N1})(b_{12},b_{22},\cdots,b_{N1})\cdots(b_{1L},b_{2L},\cdots,b_{NL})\). #Though bad root is copied after this, \(\Delta=(\delta_{11}, \cdots, \delta_{N1})\cdots(\delta_{1L},\cdots,\delta_{NL})\)is defined as the ascension ranges as: \(\forall j~\delta_{ij}=\begin{cases}c_i-r_i&(i\lt t)\\0&(i \geq t)\end{cases}\). #As the flag if the each elements of the bad part ascend, decide a pre-ascending matrix \(A'=(a'_{11}, a'_{21}, \cdots, a'_{N1})(a'_{12}, a'_{22}, \cdots, a'_{N2})\cdots(a'_{1L}, a'_{2L}, \cdots, a'_{NL})\) as the 'bad part ascending rule' of the rule set. #As the ascending modification rule of the rule set, decide an ascending matrix \(A\) with the pre-ascending matrix \(A'\). #With the value of the bracket \(n\), combine the \(B_1, B_2, \cdots, B_n\) which is defined as below into the right of the matrix. *\(B_1 = B + A \otimes \Delta\) *\(B_{k+1} = B_k + A \otimes \Delta\) *\(\otimes\) is the element-wise product as below: \((a_{11},\cdots, a_{N1})\cdots(a_{1L},\cdots, a_{NL}) \otimes (b_{11},\cdots, b_{N1})\cdots(b_{1L},\cdots, b_{NL}) \) \(= (a_{11}b_{11},\cdots, a_{N1}b_{N1})\cdots(a_{1L}b_{1L},\cdots, a_{NL}b_{NL})\) That's all. After the repetitions of the expansion above, The value of the bracket when the matrix is empty is the large number. bad root searching rules Left method #If there exists a column \(M=(m_1, \cdots, m_N)\) which meets \(m_k > c_k\) in the row \(t\) and any upper row \(k \leq t\), and which is in left side of \(c\), let the right-side column for \(M=(m_1, \cdots, m_N)\) be the bad root \(R\). If it is not found, the bad root is not found. ---- Upper-branch-ignoring-model *''the ancestor of the \(c\)'' is defined as \(c\) itself or the ancestor of the parent of \(c\) recursively. *''the parent of the \(c\)'' is the rightmost element \(p\) which meets all of below recursively: #\(p\) is in the same row of \(c\). #\(p\) is in the left side of \(c\). #\(p\) is smaller than \(c\). #\(p\) is in the top row, or y is in the same column as the ancestor of \(c'\). (\(c'\) is the element in the next row up of \(c\).) Then, the bad root \(R\) is the column, in which there is the parent of the lowermost non-zero element of the rightmost column. If the parent is not found, the bad root is not found and end. ---- Concestor method *''the ancestor of the \(c\)'' is defined as \(c\) itself or the ancestor of the parent of \(c\) recursively. *''the parent of the \(c\)'' is the rightmost element \(p\) which meets all of below recursively: #\(p\) is in the same row of \(c\). #\(p\) is in the left side of \(c\). #\(p\) is smaller than \(c\). Then, the bad root \(R\) is the column, in which there is the parent of the lowermost non-zero element of the rightmost column. If the parent is not found, the bad root is not found and end. ---- bad part ascending rules All branches enabled *\(\forall i,j(a'_{ij}=1)\) ---- BM2-based According to the index of column \(j\), define the column which is in the uppermost low and which is in the left side of the column \(j\) and in which there is the leftmost element which is smaller than the value of the uppermost element of column \(j\) be the 'parent column \(p(j)\) of the column \(j\)'. For all the combination of \(i, j\) which meets \(j=1 \lor (r_i \lt b_{ij} \land p(j)\mathrm{exists} \land a'_{ip(j)}=1) \), \(a'_{ij}=1\), otherwise \(a'_{ij}=0\) ---- Upper-branch-ignoring-model *''the ancestor of the \(c\)'' is defined as \(c\) itself or the ancestor of the parent of \(c\) recursively. *''the parent of the \(c\)'' is the rightmost element \(p\) which meets all of below recursively: #\(p\) is in the same row of \(c\). #\(p\) is in the left side of \(c\). #\(p\) is smaller than \(c\). #\(p\) is in the top row, or y is in the same column as the ancestor of \(c'\). (\(c'\) is the element in the next row up of \(c\).) For all \(i, j\) which meet \(r_i\) is the ancestor of \(b_{ij}\), \(a'_{ij}=1\), otherwise \(a'_{ij}=0\). ---- Ascending modification rules no modify \(\forall ij (a_{ij}=a'_{ij})\) ---- All 1 or (1,0,…,0) For all \(j\), define \(a_{ij}\) from \(a'_{ij}\) as below: * If \(\forall i(a'_{ij}=1)\) then \(\forall i(a_{ij}=1)\) otherwise \(a_{ij}=\begin{cases}1&(i=1)\\0&(i \gt 1)\end{cases}\). ---- All 1 or All 0 For all \(j\), define \(a_{ij}\) from \(a'_{ij}\) as below: * if \(\forall i(a'_{ij}=1)\) then \(\forall i(a_{ij}=1)\), otherwise \(\forall i(a_{ij}=0)\). references Category:Blog posts